/**
 * Created with IntelliJ IDEA.
 * Description:
 */
public class HashBuck {
    class Node{
        public Node next;
        public int value;
        public int key;

        public Node(int value, int key) {
            this.value = value;
            this.key = key;
        }
    }
    public Node[] array =new Node[10];
    public int numsize;
    public static final double LOAD_FACTOR =0.75d;
    //采用尾插法
    public void put(int key,int value){
        Node node =new Node(key,value);
        int index = key%array.length;
        Node cur =array[index];
        if (cur==null){
            array[index] =node;
            numsize++;
            return;
        }
        Node pre =null;
        //看是否有重复的 key 值
        while (cur!=null){
            if (cur.key==key){
                cur.value =value;
                return;
            }
            pre =cur;
            cur=cur.next;
        }
        pre.next =node; //尾插法
        numsize++;
        //如果超过负载因子就得扩容
        if (numsize*1.0/array.length>=LOAD_FACTOR){
            resize();
        }
    }

    public int get(int key){
        int index =key%array.length;
        Node cur =array[index];
        while (cur!=null){
            if (cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return -1;
    }



    private void resize() {
        Node[] newArray =new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            Node cur =array[i];
            while (cur!=null){
                int key =cur.key;
                int index =key%newArray.length;
                Node curN =cur.next;
                cur.next =newArray[index];
                newArray[index] =cur;
                cur =curN;
            }
        }
        array =newArray;
    }

    //采用头插法
    public void put1(int key,int value){
        Node node =new Node(key,value);
        int index = key%array.length;
        Node cur =array[index];
        //看是否有重复的 key 值
        while (cur!=null){
            if (cur.key==key){
                cur.value =value;
                return;
            }
            cur=cur.next;
        }
        //头插法
        node.next =array[index];
        array[index] =node;
        numsize++;
    }
}
